package ReusableCode;

import java.math.*;
import java.util.*;

public class MathFunctions {
	
	public static int safeLongToInt(long l) {
	    if (l < Integer.MIN_VALUE || l > Integer.MAX_VALUE) {
	        throw new IllegalArgumentException
	            (l + " cannot be cast to int without changing its value.");
	    }
	    return (int) l;
	}
	
	public static long GCD(long a, long b) 
	{
		if (b==0) return a;
		return GCD(b,a%b);
	}
	
	public static long reverseNumber(long num)
	{
		long rev = 0;
		long last = 0;
		
		while (num != 0)
		{    
			last = num % 10;
		     
			{     
				rev = rev * 10 + last;
			}
		    num = num / 10; 
		}
		
		return rev;
	}
	
	//Get all divisors of a number.
	public static List<Long> getDivisors(long num)
	{
		List<Long> divisors = new ArrayList<Long>();
		
		for(long i = 1; i*i <= num; i++)
		{
			if(num%i==0) 
			{
				if(num/i!=i)
				{
					divisors.add(num/i);
				}
				
				divisors.add(i);
			}
		}
		
		return divisors;
	}
	
	//Get all divisors of a number.
		public static List<long[]> getDivisorPairs(long num)
		{
			List<long[]> divisors = new ArrayList<long[]>();
			
			for(long i = 1; i*i <= num; i++)
			{
				long pair[] = new long[2];
				if(num%i==0) 
				{
					if(num/i!=i)
					{
						pair[1] = (num/i);
					}
					
					pair[0] = i;
					
					divisors.add(pair);
				}
			}
			
			return divisors;
		}
	
	//Get all divisors of a number.
	public static List<Long> getProperDivisors(long num)
	{
		List<Long> divisors = new ArrayList<Long>();
		
		for(long i = 1; i*i <= num; i++)
		{
			if(num%i==0) 
			{
				if(num/i!=i && i!=1)
				{
					divisors.add(num/i);
				}
				
				divisors.add(i);
			}
		}
		
		return divisors;
	}
	
	//Get all divisors of a number.
	public static List<Integer> getProperDivisors(int num)
	{
		List<Integer> divisors = new ArrayList<Integer>();
		
		for(int i = 1; i*i <= num; i++)
		{
			if(num%i==0) 
			{
				if(num/i!=i && i!=1)
				{
					divisors.add(num/i);
				}
				
				divisors.add(i);
			}
		}
		
		return divisors;
	}
	
	public static boolean isAbundant(int num)
	{
		long sum = MathFunctions.getSetSum(MathFunctions.getProperDivisors(num));
		
		if(sum > num)
		{
			return true;
		}
		
		return false;
	}
	
	public static boolean hasSquareDivisor(BigInteger num)
	{
		for(BigInteger i = new BigInteger("2"); i.multiply(i).compareTo(num)<0; i = i.add(BigInteger.ONE))
		{
			if(num.mod(i).equals(BigInteger.ZERO)) 
			{
				if(MathFunctions.isSquare(num.divide(i)))
				{
					return true;
				}
				else if(MathFunctions.isSquare(i))
				{
					return true;
				}
			}
		
		}
		
		return false;
	}
	
	//Returns true if the given number has no divisors that are the square of a prime.
	public static boolean isSquareFree(long num)
	{
		//Get primes.
		int max = (int)Math.sqrt(num) > 0 ?  (int)Math.sqrt(num) : 1;
		List<Integer> primes = PrimeFunctions.GetPrimes(max);
		
		for(long i = 1; i*i <= num; i++)
		{
			if(num%i==0) 
			{
				long a = i, b = num/i;
				
				//Check a.
				long temp = (long) Math.sqrt(a);
				if((a == temp*temp) && primes.contains(MathFunctions.safeLongToInt(temp)))
				{
					return false;
				}
				
				//Check b.
				temp = (long) Math.sqrt(b);
				if((b == temp*temp) && primes.contains(MathFunctions.safeLongToInt(temp)))
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	//Returns true if the given number has no divisors that are the square of a prime.
	public static boolean isSquareFree(long num, List<Integer> primes)
	{
		for(long i = 1; i*i <= num; i++)
		{
			if(num%i==0) 
			{
				long a = i, b = num/i;
				
				//Check a.
				long temp = (long) Math.sqrt(a);
				if((a == temp*temp) && primes.contains(MathFunctions.safeLongToInt(temp)))
				{
					return false;
				}
				
				//Check b.
				temp = (long) Math.sqrt(b);
				if((b == temp*temp) && primes.contains(MathFunctions.safeLongToInt(temp)))
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	public static boolean isSquare(BigInteger n)
	{
		BigInteger a = BigInteger.ONE;
		BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
		while(b.compareTo(a) >= 0) {
			BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
			if(mid.multiply(mid).compareTo(n) > 0) 
				b = mid.subtract(BigInteger.ONE);
			else
				a = mid.add(BigInteger.ONE);
		}
		
		if(a.subtract(BigInteger.ONE).multiply(a.subtract(BigInteger.ONE)).equals(n))
		{
			return true;
		}
		
		return false;
	}
	
	//Gets the nth root or returns -1 if the root is not an integer.
	public static RootReturn getNthRoot(BigInteger n, int root)
	{
		BigInteger a = BigInteger.ONE;
		BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
		BigInteger mid = BigInteger.ONE;
		
		//Binary search to find value.
		while(b.compareTo(a) >= 0) {
			mid = new BigInteger(a.add(b).shiftRight(1).toString());
			BigInteger midToTheN = BigInteger.ONE;
			
			for(int i = 0; i < root; i++)
			{
				midToTheN = midToTheN.multiply(mid);
			}
			
			int compare = midToTheN.compareTo(n);
			
			if(compare > 0)
			{
				b = mid.subtract(BigInteger.ONE);
			}
			else if(compare == 0)
			{
				return new RootReturn(mid, true);
			}
			else
			{
				a = mid.add(BigInteger.ONE);
			}
		}
		
		return new RootReturn(mid, false);
	}
	
	public static int[] getDigits(long num)
	{
		int length = String.valueOf(num).length();
		int digits[] = new int[length];
		
		for(int i = 0; i < length; i++)
		{
			digits[i] = getDigit(num,i+1);
		}
		
		return digits;
	}
	
	public static int numberOfDigits(long num)
	{
		return String.valueOf(num).length();
	}
	
	public static int numberOfDigits(BigInteger num)
	{
		return num.toString().length();
	}
	
	public static HashSet<Integer> getDigitsHash(long num)
	{
		int length = String.valueOf(num).length();
		HashSet<Integer> digits = new HashSet<Integer>();
		
		for(int i = 0; i < length; i++)
		{
			digits.add(getDigit(num,i+1));
		}
		
		return digits;
	}
	
	//Gets the digit of a number from left to right.
	public static int getDigit(long num, int digit)
	{
		long number = num;
		int ret = -1;
		int count = 0;
		
		while ((count < digit) && (number > 0)) {
		    ret = (int)(number % 10);
		    number = number / 10;
		    count++;
		}
		
		return ret;
	}
	
	public static long arrayToLong(int array[])
	{
		long value = 0;
		
		for(int i = 0; i < array.length; i++)
		{
			
			value += (array[i] * (Math.pow(10, array.length-i-1)));
		}
		
		return value;
	}
	
	public static long getSetSum(List<Integer> set)
	{
		long sum = 0;
		
		for(int i = 0; i < set.size(); i++)
		{
			sum += set.get(i);
		}
		
		return sum;
	}
	
	public static long getSetSumLong(List<Long> set)
	{
		long sum = 0;
		
		for(int i = 0; i < set.size(); i++)
		{
			sum += set.get(i);
		}
		
		return sum;
	}
	
	public static BigInteger getSetSum(ArrayList<BigInteger> set)
	{
		BigInteger sum = BigInteger.ZERO;
		
		for(int i = 0; i < set.size(); i++)
		{
			sum = sum.add(set.get(i));
		}
		
		return sum;
	}
	
	public static boolean isPanDigital(long num)
	{
		long number = num;
		List<Integer> digits = new ArrayList<Integer>();
		
		while(number > 0)
		{
			digits.add((int)number%10);
			number /= 10;
		}
		
		for(int i = 1; i <= digits.size(); i++)
		{
			if(!digits.contains(i))
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static List<Long> removeDuplicates(List<Long> vals)
	{
		Map<Long, Boolean> hash = new HashMap<Long, Boolean>();
		List<Long> list = new ArrayList<Long>();
		
		for(int i = 0; i < vals.size(); i++)
		{
			long val = vals.get(i);
			
			if(!hash.containsKey(val))
			{
				hash.put(val, true);
				list.add(val);
			}
		}
		
		return list;
	}
	
	public static int[] reverseArray(int array[])
	{
		for(int i = 0; i < array.length/2; i++)
		{
			int temp = array[i];
			array[i] = array[array.length-1-i];
			array[array.length-1-i] = temp;
		}
		
		return array;
	}
	
	public static int[] listToArray(List<Integer> list)
	{
		int[] array = new int[list.size()];
		
		for(int i = 0; i < array.length; i++)
		{
			array[i] = list.get(i);
		}
		
		return array;
	}
	
	public static List<Integer> arrayToList(int[] ints)
	{
	    List<Integer> intList = new ArrayList<Integer>();
	    for (int index = 0; index < ints.length; index++)
	    {
	        intList.add(ints[index]);
	    }
	    
	    return intList;
	}
	
	public static boolean isPalindrome(long num)
	{
		return MathFunctions.isPalindrome(MathFunctions.getDigits(num));
	}
	
	public static boolean isPalindrome(int pal[])
	{	
		for(int i = 0; i < pal.length/2; i++)
		{
			if(pal[i] != pal[pal.length-i-1])
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static boolean isPalindrome(long num, int base)
	{
		if(base == 10)
		{
			return isPalindrome(num);
		}
		else if(base == 2)
		{
			int totalBits = Long.bitCount(num);
			int count = 0, i = 0;
			List<Integer> digits = new ArrayList<Integer>();
			
			while(count < totalBits)
			{
				if ((num  & (1L << i)) == 0)
				{
					digits.add(0);
				}
				else
				{
					digits.add(1);
					count++;
				}
				
				i++;
			}
			
			int digs[] = MathFunctions.listToArray(digits);
			
			return isPalindrome(digs);
		}
		
		return false;
	}
	
	public static List<Long> getPalindromes(long max)
	{		
		List<Long> palindromes = new ArrayList<Long>();
		
		palindromes.add(0L);
		for(int i = 0; i < 10; i++)
		{
			palindromes.add((long)i);
		}
		
		for(int i = 1; i <= max; i++)
		{
			int digits[] = MathFunctions.getDigits(i); //MathFunctions.reverseArray()
			
			long temp = generatePalindrome(digits);
			if(temp>=0){
				palindromes.add(temp);
			}
			palindromes.addAll(generatePalindromes(digits));
		}
		
		//Sort the palindrome list.
		Collections.sort(palindromes);
		palindromes = MathFunctions.removeDuplicates(palindromes);
		
		return palindromes;
	}
	
	private static long generatePalindrome(int digits[])
	{
		int palDigits[] = new int[(digits.length*2)];
		
		if(digits[0]==0)
		{
			digits = MathFunctions.reverseArray(digits);
		}
		
		for(int i = palDigits.length-1; i >= 0; i--)
		{
			if (i > (digits.length-1))
			{
				palDigits[i] = digits[palDigits.length-1-i];
			}
			else
			{
				palDigits[i] = digits[i];
			}
		}
		
		long ret = MathFunctions.arrayToLong(palDigits);
		
		if(!isPalindrome(ret))
		{
			ret = -1;
		}
		
		return ret;
	}
	
	private static List<Long> generatePalindromes(int digits[])
	{
		List<Long> pals = new ArrayList<Long>();
		int palDigits[] = new int[(digits.length*2)+1];
		
		if(digits[0]==0)
		{
			digits = MathFunctions.reverseArray(digits);
		}
		
		for(int i = 0; i < palDigits.length; i++)
		{
			if (i > (digits.length-1))
			{
				if(i!=(palDigits.length/2))
				{
					palDigits[i] = digits[palDigits.length-1-(i)];
				}
			}
			else 
			{
				palDigits[i] = digits[i];
			}
		}
		
		for(int j = 0; j < 10; j++)
		{
			palDigits[(palDigits.length/2)] = j;
			long ret = MathFunctions.arrayToLong(palDigits);
			if(MathFunctions.isPalindrome(ret))
			{
				pals.add(ret);
			}
		}
		
		return pals;
	}
	
	public static long getFactorial(long num)
	{
		if(num > 20L && num > 0)
		{
			return -1L;
		}
		else if(num == 0)
		{
			return 1;
		}
		
		long ret = 1;
		
		for(int i = 1; i <= num; i++)
		{
			ret *= i;
		}
		
		return ret;
	}
	
	public static List<Long> getNumberRotations(long num)
	{
		int[] digits = MathFunctions.getDigits(num);
		int size = digits.length;
		List<Long> rotations = new ArrayList<Long>();
		
		for(int i = 0; i < size; i++)
		{
			int[] number = new int[size];
					
			for(int j = 0; j < size; j++)
			{
				number[j] = digits[(i+j)%size];
			}
			
			rotations.add(MathFunctions.arrayToLong(number));
		}
		
		return rotations;
	}
	
	public static List<Long> getNumberPermutations(long num)
	{
		List<int[]> perm = getPermutations(MathFunctions.getDigits(num));
		List<Long> perms = new ArrayList<Long>();
		
		for(int i = 0; i < perm.size(); i++)
		{
			perms.add(MathFunctions.arrayToLong(perm.get(i)));
		}
		
		return perms;
	}
	
	private static List<int[]> getPermutations(int digits[])
	{		
		if(digits.length==1) 
		{
			List<int[]> ret =  new ArrayList<int[]>();
			ret.add(digits);
			return ret;
		}
		else if(digits.length>1)
		{
			List<int[]> perm = getPermutations(Arrays.copyOfRange(digits, 1, digits.length));
			List<int[]> ret = new ArrayList<int[]>();
			int digit = digits[0];
			
			for(int i = 0; i < perm.size(); i++)
			{	
				int arr[] = perm.get(i);
				for(int j = 0; j < digits.length; j++)
				{
					int digs[] = new int[digits.length];
					
					for(int k = 0; k < digits.length; k++)
					{
						if (j==k)
						{
							digs[k] = digit;
						}
						else if (k<j)
						{
							digs[k] = arr[k];
						}	
						else
						{
							digs[k] = arr[k-1];
						}
					}
					if(!ret.contains(digs))
						ret.add(digs);
				}
			}
			
			return ret;
			
		}
		
		return null;
	}	
}